1. Field of the Invention
The present invention relates to the rendering of images for printing on printers, especially page printers such as laser printers and more especially color laser printers.
2. State of the Art
In recent years, increasingly greater computing power has been made available in desktop computers. At the same time, the sophistication of printing capabilities available to the average computer user has also increased. Laser printers offering near-typeset quality are commonplace in the business sector. Moderate-resolution color printers offering reasonable color performance have begun to be affordable by a large class of users.
In accordance with the foregoing trend, the demand for photo-realistic and near-photo-realistic color printers is expected to increase. Presently, color printers are generally one of several different types: thermal transfer, dye sublimation, ink jet, and laser. Thermal transfer offers lower quality and speed. Dye sublimation printers offer good quality but are slow and expensive. Inexpensive ink jet printers are slow and produce low-quality output. More expensive ink jet printers, although still slow, produce good quality output for larger pictures. As compared to color ink-jet printers, however (which account for the bulk of color printers presently sold), color laser printers hold great promise for achieving photo-realistic color output at high printing speed and low cost per copy.
Printers (as opposed to plotters) operate by forming small dots (also referred to as pixels) in a pattern on the page. In laser printers, these small dots are formed by scanning a laser beam in a scan direction across a photosensitive drum. (The image on the photosensitive drum is then developed, transferred to, and fixed on the actual page.) Typically, scanning is accomplished using a rotating polygonal mirror on which the laser is shined. Each facet of the mirror causes the laser beam to be scanned once across the photosensitive drum. During a scan, the laser beam is modulated, i.e., turned on and off, so as to either expose a dot at a particular location within the scan or not expose a dot. The photosensitive drum moves at a constant speed during scanning, in a paper advance direction, so as to cause successive scans to be displaced. The amount by which successive scan lines are displaced is called the line pitch.
The collection of dots in a scan line is referred to as a raster scan line. A group of successive scan lines is referred to as a band, or scan line swath. The collection of all the dots in all of the scan lines on a page is called a raster image. A collection of dots to be printed within a particular (and usually rectangularly shaped) area of the page is referred to as a pixel map. For example, on a color brochure, a company's logo might be defined as a pixel map and printed across the top of the page.
As opposed to the ink-jet printer, which is an example of a banded (scan-line swath) device, a laser printer is inherently a page device. That is, once laser printing has started (i.e., laser scanning of the drum has begun), it cannot be stopped or paused but must continue to completion without interruption. Although ink jet printers have certain real time data requirements with respect to a single band, the laser printing operation has more stringent real time data requirements that must be met for a satisfactory print to be produced, in that data has to be available for the entire page.
Conventionally, a laser printer consists of a printer controller and a print engine. The print engine exposes and develops dots on the physical page. The printer controller provides printer commands and print data to the print engine to cause it to print the desired page. The printer controller receives from an application program a page description in a page description language (PDL) such as Postscript.TM. from Adobe Systems, for example.
Ordinarily, printer controllers receive PDL statements from an application program and interpret those by means of a PDL interpreter. PDL interpreters usually preprocess PDL statements by computing the actual shapes and positions for the graphic objects associated with the statement and then apply those graphic objects to the page raster image by means of a marking interface. This interface consists of a generally proprietary, but usually well-understood, set of operations called rasterization requests. The Marking Interface passes the rasterization requests to a subsequent rasterization process. For example, a PDL interpreter might use the following set of rasterization requests (denoted "RAST") to describe the raster image for a page:
RAST1: Apply a rectangular pixel array of a given color (for text application).
RAST2: Fill in a trapezoidal area with a given color (area graphics).
RAST3: Expand (magnify, rotate, scale, skew, etc.) an image and apply it to the raster.
The present invention is also applicable to graphic environments such as Microsoft Windows, Apple Macintosh, etc., from which graphic commands (unlike PDL statements) are issued. These graphics commands can be similarly processed into rasterization requests by graphic command processors. And, in some cases, these environments directly generate rasterization requests of a well-known and publicly available format.
In conventional PDL interpreters, rasterization requests are typically organized in one of three principal ways. A first way of organizing rasterization requests involves sorting requests into a display list. Requests are commonly sorted in increasing order of y coordinate. For example, the following requests might be received from a PDL source, in the order listed:
1. Describe triangle PA0 2. Draw it at (x3, y2) PA0 3. Choose Font 1 PA0 4. Set string "AB" at (x1, y1) PA0 5. Choose Font 2 PA0 6. Set string "C" at (x4, y3)
The corresponding page, together with a sorted display list, is shown in FIG. 1. As seen therein, the display list is sorted first by y coordinate, then, secondarily, by x coordinate.
A second way of organizing rasterization requests involves dividing the page into bands as shown in FIG. 2. For each band, a separate display list is built. This technique and the previous technique are similar in that a page may be considered as a tall band. Collectively, the display lists for bands may be larger, however, than the display list for a full page (because the same print element may overlap bands, requiring it to be included in each). Since the size of the display list is, in principle, unbounded, a sequence of display lists may be generated instead, thus requiring multiple rasterization passes over each band. In either case the resulting raster is the same.
A third way of organizing rasterization requests involves simply creating an unsorted set of requests. This manner of organization requires that the rasterizer system keep an increasing list of randomly accessible scan lines. Various ways of saving memory have been devised, for example by only allocating those scan lines that are really being used, and even allocating rectangular patches of the raster on demand. In general, however, the rasterizer must effectively have access to a full bitmap. A significant advantage of this approach is that no display list needs to be created.
A single high-resolution, full-color image can require hundreds of megabytes of memory to store. In order to print such an image using a color laser printer, the entire image must be rendered and stored in memory at a single time to avoid the possibility of delays in supplying image data to the print engine (under-runs).
This requirement of laser printing imposes extreme memory storage and memory bandwidth requirements on a high-resolution, full-color laser printer. Such printers have therefore been quite expensive. In the prior art, the entire image or at least an image band is rasterized and stored. The stored rasterized image or image band is then retrieved and compressed. Finally, the compressed image or image band is then stored for later expansion and output to the print engine. As a result, each pixel of the image is handled multiple times. Both memory requirements and memory bandwidth requirements are large.